1. Technical Field
This invention relates to a compiler, particularly to a method for reducing the number of array range checks in a compiler to increase execution speed of a program. An array range check is a check on whether an array access in a program is exceeding a range of the array.
2. Prior Art
There is a method for eliminating array range checks by using data-flow analysis (see xe2x80x9cOptimizing array bound checks using flow analysisxe2x80x9d, R. Gupta, ACM Letters on Programming Languages and Systems, 2(1-4), pp. 135 to 150, March-December, 1993, etc.). This method eliminates an array range check by the following two-phased process. Namely, (1) Insert a check near the beginning in program execution order so as to decrease array range checks. (2) Eliminate redundant array range checks. The advantage of this method is that it can apply to other places than a loop. However, it has its disadvantages, namely, the range in which it can eliminate array range checks is narrow and it can only apply to a language whose specification defines that it is a error to exceed a range.
As to other background arts, there is a method of loop conversion by loop splitting. This is a method of dividing a loop into three portions: a checked portion, an unchecked portion of the lower bound value and a checked portion of the upper bound value. For instance, a program of Table 1 is converted to of Table 2.
If divided into three portions in this way, the second for loop can omit a range check. As a disadvantage of this method, if an array access in a loop is simple, the code size merely becomes three times larger, while, as to a case where there are a plurality of array base variables, there are more portions to be divided into and the code size becomes accordingly larger.
The Java language (Java is a trademark of Sun Microsystems, Inc.) is, as its specification, capable of detecting an access exceeding an array range, and when there is no user-defined exception handler, moving control to an invoked method after getting out of a method in which an exception occurred, or when there is a user-defined exception handler, moving the process to the exception handler. Accordingly, an array range check is essential since occurrence of an exception may be described as a correct operation in a program. However, an array range check slows execution speed compared with a language which does not require such a check. In an actual program, there is an array access to ensure that there is no access exceeding a range, and thus elimination of such redundant array range checks greatly contributes to improved performance. In addition, it is more desirable if the range of optimization can be expanded from the viewpoint of ensuring execution order between occurrence of an exception and a process with a side effect such as an assignment of a value to an array.
An object of the present invention is to reduce the number of array range checks and increase execution speed.
Another object of the present invention is to perform a two-phased check, namely to perform a wide range check by combining a plurality of array range checks, and perform a strict range check in the case that the wide range check fails, so as to provide a method for reducing the number of array range checks at execution time and allowing execution at increased speed.
A further object of the present invention is to provide a method for versioning by using information about array accesses which are always performed even if passing through any execution path in a loop. Versioning is a process which, at compilation time, (1) classifies execution states of a code of a certain portion of a program into several states, and (2) generates at execution time a check code to classify such states and an execution code of the certain portion of the program for each state.
The present invention to reduce the number of array range checks is, in a wider, to combine a plurality of array range checks and generate a code for a combined array range checks, and to generate a code for an array range check included in the plurality of array range checks in the case that the combined array range check is unsuccessful. These codes are stored in a storage and executed later by a processor. To make such a concept more specific, it becomes the following three forms.
In the first form, in the case of generating a code for an array range check for an array access in a program, it is executed, comprises: a first step of generating and storing in a storage (for instance, main memory) a first code for storing in one or a plurality of storage areas (for instance, flags of a processor) a result of combined array range check which combines a plurality of array range checks corresponding to a plurality of array accesses (for instance, VERSION_OR[B] in the Embodiments); and a second step of generating and storing in a storage a third code (for instance, a zero-cycle branch instruction in Power PC (a trademark of International Business Machines Corp.)) for checking the storage area and for invalidating a second code (an array range check which must be executed so as not to be incorrectly executed, unless invalidated by the third code) for an array range check included in the plurality of array range checks if the storage area indicates the combined array range check is successful. For instance, when using a processor whose flag can be used as a register, the second code can be invalidated at high speed and the number of array range checks can be reduced without increasing a code size so much. Using a flag as a register means that the flag can be kept without having its content arbitrarily destroyed by an arithmetical instruction, etc.
The aforementioned first step may comprise the steps of: combining array range checks for a plurality of array accesses according to a predetermined condition and storing in a storage information about a combined array range check; and allocating the combined array range check to a storage area.
In the case of versioning in the first form of the present invention, there is the further executed step of:
generating and storing in a storage a code which refers to the storage area storing the result of the combined array range check which is a condition of the versioning, if the storage area indicates that the combined array range check is successful, branches into versions not including a code for array range check included in the combined array range check, and if the storage area indicates that the combined array range check is unsuccessful, branches into versions including the second and third codes. This allows faster execution than ever even in the case that the combined array range check which is a condition of the versioning is unsuccessful.
In the second form of the present invention, in the case of generating a code for an array range check for an array access in a program, there are the performed steps of: generating and storing in a storage a second portion (for instance, part B of the Embodiments) for performing an array range check for necessary range corresponding to the array access included, the second portion corresponding to a first portion to be processed (for instance, part A of the Embodiments) of the program; performing for the first portion, an optimization process for array range checks and an elimination process for redundant array range checks regardless of the existence of a side effect instruction so that a side effect is caused by moving an array range check issuing an exception before the side effect instruction, and storing in a storage for each basic block in the first portion information about necessary array range checks (or unremovable array range checks); and generating and storing in a storage a conditional branch code for performing the necessary array range check and for jumping to a basic block in the second portion if the array range check is not successful, the basic block corresponding to a basic block which includes the unsuccessful array range check. The second form of the present invention can be performed even if the first form cannot be performed. Also, since the first portion after an optimization and an elimination for redundant array range checks is executed until there is an array access for which an array range check is essentially unsuccessful, the number of array range checks can be reduced.
In the third form of the present invention, in the case of versioning a loop in a program, there are the executed steps of: collecting first set information (VERSION_AND[B] in the Embodiments) of array range checks for array accesses which are always performed even if passing through any execution path in a loop, and storing in a storage a collection result; by using the collection result, generating and storing in a storage a check code for the versioning; eliminating a redundant array range check by using the collection result, and generating and storing in a storage a version in the case that an array range check by the check code is successful, the version including a code for unremovable array range check; and generating and storing in a storage a version in the case that an array range check by the check code is unsuccessful. Thus, only in the case that an array range check is always unsuccessful in a loop, a version in the case that an array range check by the check code is unsuccessful is executed so that reduction in the number of array range checks can be expected.
While the above was a case of two versions, it is also possible to divide into three versions and the following steps are executed in this case. Namely, the steps of: collecting second set information (VERSION_OR[B] in the Embodiments) of array range checks not restrictively for array range checks for array accesses which are always performed even if passing through any execution path in the loop, and storing in a storage a second collection result; generating and storing in a storage a second check code for further versioning a version in the case that an array range check by the check code is successful by using third set information, the information being the second set information after removing array range checks included in the first set information; and eliminating a redundant array range check by using the second collection result, and generating and storing in a storage a version in the case that an array range check by the second check code is successful, the version including a code for unremovable array range checks. Meanwhile, the version in the case that an array range check by the check code is successful is the version in the case that an array range check by the second check code is unsuccessful. By doing so, the code size becomes three times larger, while, if the original code is little, further reduction in the number of array range checks at execution time can be expected.
It is also possible to combine the first and third forms of the present invention, and for instance, there can be the further executed steps of: in the case of two versions, generating and storing in a storage a code for storing in a flag of a processor which executes the generated code a result of an array range check, the check based on the unremovable array range check and a range of an index variable; and checking the flag, and if the flag indicates success of the unremovable array range check, generating and storing in a storage another code for invalidating the code for unremovable array range check. This can speed up processing since, in the case that an array range check by the check code is successful, only a flag may be checked omitting an actual array range check.
If a flag of a processor is used to obtain an effect similar to the above, it is thinkable to execute steps of: collecting second set information (VERSION_OR[B] in the Embodiments) of array range checks not restrictively for array range checks for array accesses which are always performed even if passing through any execution path in the loop, and storing in a storage a second collection result; generating and storing in a storage a code for storing in a flag of a processor which executes the generated code a result of third set information (VERSION_OR[B]-VERSION_AND[B] in the Embodiments), the information being the second set information after removing array range checks included in the first set information; and checking the flag, and if the flag indicates success of an array range check included in the third set information, generating and storing in a storage another code for invalidating the code for unremovable array range check in the case of two versions.
Also, to combine the first and third forms of the present invention in the case of no versioning, in the first step described in the process for the first form of the present invention, there are the executed steps of: collecting first set information (VERSION_AND[B] in the Embodiments) of array range checks for array accesses which are always performed even if passing through any execution path in a certain portion of the program, and storing in a storage a collection result; collecting second set information (VERSION_OR[B] in the Embodiments) of array range checks not restrictively for array range checks for array accesses which are always performed even if passing through any execution path in the certain portion, and storing in a storage a second collection result; and allocating array range checks included in the second set information to one storage area and allocating array range checks in third set information to one or a plurality of storage areas, the third information being the second information after removing array range checks included in the first set information. This can effectively eliminate array range checks.
As above, the present invention has been represented as a flow of processing, while it is also possible to implement it by a computer or a computer program, or a dedicated circuit or device which execute the above process. Moreover, in the case of implementing it by a computer program, the computer program may be stored on a storage medium such as a CD-Rom, a floppy disk or a hard disk.